package org.algorithm.Backtracking.leetcode93;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        Solution test = new Solution();
        test.restoreIpAddresses("25525511135");
    }

    List<String> res = new ArrayList<>();

    StringBuilder item = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {

        backtracking(s, 0, 0);

        return res;
    }

    private void backtracking(String s, int partCount, int index) {
        if (partCount == 4 && index == s.length()) {
            res.add(new String(item));
            return;
        }

        if (index == s.length() || partCount == 4) {
            return;
        }

        for (int i = 1; i <= 3 && index + i < s.length(); i++) {
                String str = s.substring(index,index+i);
                if (isValid(str)){
                    // item.length-1表示没有添加新元素之前的最大下标，delete操作需要删除 以item.length-1的下一个下标为开始（即item.length-1+1)
                    // 到结尾的字符串
                    int startIndex = item.length();
                    if (partCount>0){
                        item.append(".");
                    }
                    item.append(str);
                    partCount++;

                    backtracking(s,partCount,index+i);

                    partCount--;
                    item.delete(startIndex,item.length());
                }
        }
    }

   private boolean isValid(String str){
        //需要考虑0
        if ( str.length()>1 && str.startsWith("0")){
            return false;
        }

       Integer num = Integer.valueOf(str);
        if (num>=0 && num<=255){
            return true;
        }
       return false;
   }

}
